package PersonStu.sanqi;

/**
 * @Author by KoVaVo
 * @Date 2023-01-01 14:29
 * @Desc: 一个机器人在一个顺序数组上走，在中间的位置往左或者往右，
 * 在最左边只能往右了
 * 在最右边只能往左了
 * 给定一个机器人当前的位置cur，要走到p的位置，还剩下rest步可以走。返回有多少种走法。
 */
public class code_21_RobortWalk {

    public static int walk1(int N,int start,int aim,int K){
        if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
            return -1;
        }
        return process1(start,K,aim,N);
    }

    /**
     *
     * @param cur 当前的位置
     * @param rest 还剩下多少步可以走
     * @param aim 要走到的目标位置
     * @param n 有哪些位置，1-N个位置
     * @return
     */
    private static int process1(int cur, int rest, int aim, int n) {
        if(rest == 0){
            //如果没有多余的步数了，直接返回
            return cur == aim ? 1 : 0;
        }
        if(cur == 1){
            //如果来到了最左边的位置，只能往右走
            process1(2,rest - 1,aim,n);
        }
        if(cur == n){
            //如果来到了最右边的位置，只能往左走
            process1(n - 1,rest - 1,aim,n);
        }
        //如果还在中间的某个位置，可以往左或者往右
        return
                process1(cur - 1,rest - 1,aim,n)
                +
                process1(cur + 1,rest - 1,aim,n);
    }

    public static int walkCache(int N,int start,int aim,int K){
        if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
            return -1;
        }
        int [][] dp = new int[N+1][K+1];
        //构建一个dp二维数组
        for(int row = 0;row <= N;row++){
            for(int col = 0;col <= K;col++){
                dp[row][col] = -1;
            }
        }
        return processCache(start,K,aim,N, dp);
    }

    private static int processCache(int cur, int rest, int aim, int N, int[][] dp) {
        if (dp[cur][rest] != -1) {
            return dp[cur][rest];
        }
        // 之前没算过！
        int ans = 0;
        if (rest == 0) {
            ans = cur == aim ? 1 : 0;
        } else if (cur == 1) {
            ans = processCache(2, rest - 1, aim, N, dp);
        } else if (cur == N) {
            ans = processCache(N - 1, rest - 1, aim, N, dp);
        } else {
            ans = processCache(cur - 1, rest - 1, aim, N, dp) + processCache(cur + 1, rest - 1, aim, N, dp);
        }
        dp[cur][rest] = ans;
        return ans;
    }

    public static void main(String[] args) {
        int N = 7;
        int start = 3;
        int aim = 4;
        int K = 5;
        //一共7个位置，从3的位置出发要求来到4的位置，要走5步。有多少种走法。
        int i = walk1(N, start, aim, K);
        System.out.println(i);
        System.out.println("使用动态规划的方式");
        System.out.println(walkCache(N,start,aim,K));
    }
}
